class Solution {
public:
    // [0, i]中选字符串 0的个数至多为j 1的个数至多为k
    int dfs(vector<vector<vector<int>>> &memo, vector<int> &cnt0, vector<string>& strs, int i, int j, int k)
    {
        if(i<0) return 0;
        int &res=memo[i][j][k];
        if(res!=-1) return res; //记忆化搜索

        res=dfs(memo, cnt0, strs, i-1, j, k); //不选strs[i];
        int cnt1=strs[i].size()-cnt0[i];
        if(j>=cnt0[i]&&k>=cnt1) //选
            res=max(res, dfs(memo, cnt0, strs, i-1, j-cnt0[i], k-cnt1)+1);
        return res;
    }

    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<int> cnt0(strs.size());
        for(int i=0; i<strs.size(); i++) 
            cnt0[i]=ranges::count(strs[i], '0');
        
        vector memo(strs.size(), vector(m+1, vector<int>(n+1, -1))); //-1表示没有计算过
        return dfs(memo, cnt0, strs, strs.size()-1, m, n);
    }
};